#include "single_list.h"

/*打印链表*/
void print_list(single_Node **head)
{	
	int i=1;
	single_Node *p;
	p=(*head);
	if(*head==NULL)
	{
		printf("链表头为空!\n");
		return;
	}
	printf("链表长度(不包括链表头)：%d\n",(*head)->data);
	if((*head)->data==0)
		return;
	while(p->Next!=NULL)
	{
		p=p->Next;
		printf("第%d个链表:	data=%d \n",i,p->data);
		i++;
	}
	//printf("第%d个链表:	%d （最后一个） \n",i,p->data);
}

/*创建链表头*/
void create_list_head(single_Node **head)
{
	if(*head==NULL)
	{
		(*head)=(single_Node *)malloc(sizeof(single_Node));
		(*head)->data=0;
		(*head)->Next=NULL;
	}
	else
		printf("\n链表已经创建！\n");
	printf("\n链表创建成功！\n");
	
}
/*链表头判空，如果空创建链表头，链表创建：头插法*/
void insert_list_re(single_Node **head,int data)
{
	single_Node *n,*tmp;
	if(*head==NULL)
	{
		printf("链表头空，创建一个！");
		(*head)=(single_Node *)malloc(sizeof(single_Node));
		(*head)->data=0;
		(*head)->Next=NULL;
	}
	
	n=(single_Node *)malloc(sizeof(single_Node));
	tmp=(*head)->Next;
	(*head)->Next=n;
	n->Next=tmp;
	n->data=data;	
	(*head)->data+=1;
}
/*链表头判空，如果空创建链表头，链表创建：尾插法*/
void insert_list_se(single_Node **head,int data)
{
	single_Node *n,*tmp;
	if(*head==NULL)
	{
		printf("链表头空，创建一个！");
		(*head)=(single_Node *)malloc(sizeof(single_Node));
		(*head)->data=0;
		(*head)->Next=NULL;
	}
	n=(single_Node *)malloc(sizeof(single_Node));
	tmp=*head;
	while(tmp->Next!=NULL)
		tmp=tmp->Next;

	n->Next=NULL;
	tmp->Next=n;
	n->data=data;
	(*head)->data+=1;
}

/*按序号插入一个链表节点
参数1： 链表头
参数2：插入的序号
参数3：插入的数据
*/
void nu_insert_list(single_Node **head,int nu,int data)
{
	single_Node *n,*tmp;
	int i=1;
	if(nu<0&&(*head)==NULL)
	{
		return;
	}
	if((*head)->data<nu)
		printf("链表不够长！插入%d位置失败！",nu);
	tmp=*head;
	while(i<nu)
	{
		tmp=tmp->Next;
		if(tmp->Next==NULL)
		{
			printf("第%d个链表指向空！\n",i+1);			
			return;
		}
		i++;
	}
	n=(single_Node *)malloc(sizeof(single_Node));
	n->Next=tmp->Next;
	tmp->Next=n;
	n->data=data;
	(*head)->data+=1;
}

/* 按序数删除链表节点
参数1：链表头
参数2：节点序数
*/
void nu_delete_list(single_Node **head,int nu)
{
	int i=1;
	single_Node *tmp,*n;
	tmp=(*head);
	if(*head==NULL)
	{
		printf("表头空，无法操作！\n");
		return;
	}
	if(nu>(*head)->data)
	{
		printf("链表长度不够！无法删除！链表长度是：%d\n",(*head)->data);
		return;
	}
		
	if(nu==1)
	{
		printf("不可以删除链表头！！！\n");
		return;
	}
	while(i<nu)
	{
		tmp=tmp->Next;
		i++;
	}
	n=tmp->Next;
	tmp->Next=tmp->Next->Next;
	(*head)->data-=1;
	free(n);
	n=NULL;
	
}

/*整个链表删除操作*/
void delete_list(single_Node **head)
{
	int i=1;
	single_Node *tmp, *n;
	if(*head==NULL)
	{
		printf("链表头空！不需要删除！\n");
		return;
	}	
	tmp=(*head);
	printf("%p \n",tmp);
	//while((*head)->data--)
	while(tmp->Next!=NULL)
	{
		n=tmp;
		tmp=tmp->Next;
		free(n);	
		n=NULL;
	}	
	free(tmp);
	tmp=NULL;
	(*head)=NULL;
	printf("链表已删除！！！\n");
}

/*删除链表选项菜单*/
void delete_option_list(single_Node **head)
{
	int i,n;
back:
	printf("\n\n\n");
	printf("==============链表删除菜单==============\n");
	printf("1.按序号删除\n");
	printf("2.总链表都删除\n");
	printf("3.打印链表\n");
	printf("4.退出\n");
	printf("==========================================\n");
	printf("\n");
	printf("\n请输入数字：");
	scanf("%d",&i);
	printf("\n");	
	switch(i)
	{
		case 1:
back1:
			printf("\n请输入要删除链表序号：\n");
			scanf("%d",&n);
			nu_delete_list(head,n);
			printf("\n是否还需要删除？3：打印链表      2：继续删除     1：返回上层菜单    0：返回主菜单。\n");
			scanf("%d",&n);
			printf("\n");
			if(n==3)
				print_list(head);			
			if(n==2)
				goto back1;
			if(n==0)
			  	return;
				break;
		case 2:
			printf("\n确认要删除所以链表？3：打印链表      2：确认删除     1：返回上层菜单    0：返回主菜单。\n");
			scanf("%d",&n);
			printf("\n");
			if(n==3)
				print_list(head);			
			if(n==2)
				delete_list(head);
			if(n==0)
			  	return;
			break;
			break;
		case 3:
			print_list(head);
			break;
		case 4:
			return;
		default:
			return;
			break;
	}
	goto back;
}

/*单链表判断是否有循环*/
int single_list_loop_judgment(single_Node **head)
{
	single_Node *m,*n;
	int ret=0;
	if(*head==NULL)
	{
		printf("链表头空！无法判断循环！\n");
		return -1;
	}
	m=(*head);
	n=(*head);
	while(m->Next!=NULL)
	{
		if(n==m->Next)
		{
			printf("单链表有循环！\n");
			return 1;
		}

		if(m->Next!=NULL)
		{
			if(m->Next->Next!=NULL)
				m=m->Next->Next;
			else
			{
				printf("1链表指向空，没有循环！\n");
				return ret;				
			}	
		}
		else
		{
			printf("2链表指向空，没有循环！\n");		
		}

		n=n->Next;
	}
	return ret;
}

/*判断单链表是否有循环，以及找出循环的始节点位置*/
void single_list_loop_judgment_find_node(single_Node **head)
{
	int a,b;
	single_Node *L,*N;
	L=*head;
	a=0;
	while(L)
	{
		N=*head;
		b=0;
		while(N)
		{
			if(L==N)
			{
				if(a==b)
				{
					break;
				}
				else
				{
					printf("单链表有循环，循环节点位置：%d \n",b);
					return;
				}				
			}
			N=N->Next;
			b++;
		}
	L=L->Next;
	a++;
	}

}

/*但链表创建循环，sn指的是第几个节点连接尾节点*/
void single_list_create_loop(single_Node **head,int sn)
{
	single_Node *tmp,*in;
	tmp=*head;
	in=*head;
	int count=0;
	count=sn;
	if(*head==NULL)
	{
		printf("链表头空！无法创建循环！\n");
		return;
	}
	if(tmp->data < sn)
	{
		printf("超出链表长度，无法创建！\n");
		return;
	}
	if(single_list_loop_judgment(head)==1)
	{
		printf("单链表有循环无法创建！\n");
	}
	
	while(tmp->Next!=NULL)
	{
		tmp=tmp->Next;
	}

	while(sn)
	{
		in=in->Next;
		sn--;
	}
	tmp->Next=in;
	printf("单链表循环创建成功！ 尾节点指向第%d个节点！\n",count);
	
}

/*链表循环相关的操作*/
void loop_option_list(single_Node **head)
{
	int i,n;
 back:
	printf("\n\n\n");
	printf("==============链表环操作菜单==============\n");
	printf("1.创建单链表环\n");
	printf("2.判断单链表是否有环\n");
	printf("3.查找单链表环节点序号\n");
	printf("4.退出\n");
	printf("==========================================\n");
	printf("\n");
	printf("\n请输入数字：");
	scanf("%d",&i);
	printf("\n");
	switch(i)
	{
		case 1:
			printf("\n请输入尾节点要连接链表节点的序数：");
			scanf("%d",&n);
			//insert_list_se(head,n);
			single_list_create_loop(head,n);
			printf("\n");
			break;
		case 2:
			single_list_loop_judgment(head);
			break;
		case 3:
			single_list_loop_judgment_find_node(head);
			break;
		case 4:
			return;
			break;
	}
goto back;
}

/*链表插入选项菜单*/
void insert_option_list(single_Node **head)
{
	int i,n;
 back:
	printf("\n\n\n");
	printf("==============链表插入方式菜单==============\n");
	printf("1.顺序插入\n");
	printf("2.逆序插入\n");
	printf("3.按编号插入\n");
	printf("4.退出\n");
	printf("==========================================\n");
	printf("\n");
	printf("\n请输入数字：");
	scanf("%d",&i);
	printf("\n");
	switch(i)
	{
		case 1:
	back1:
			printf("\n请输入顺序建表要插入的节点数据：");
			scanf("%d",&n);
			insert_list_se(head,n);
			printf("\n是否还需要插入？    0:打印链表      1：继续插入   2：返回上层菜单    3：返回主菜单。\n");
			scanf("%d",&n);
			printf("\n");
			if(n==0)
				print_list(head);	
			if(n==1)
				goto back1;
			if(n==3)
				return;
			break;
		case 2:
		back2:
			printf("\n请输入逆序建表要插入的节点数据：");
			scanf("%d",&n);
			insert_list_re(head,n);
			printf("\n是否还需要插入？      0:打印链表     1：继续插入   2：返回上层菜单    3：返回主菜单。\n");
			scanf("%d",&n);
			printf("\n");
			if(n==0)
				print_list(head);	
			if(n==1)
				goto back2;
			if(n==3)
				return;
			break;
		case 3:
		back3:
			printf("\n请输入要插入链表位置编号：");
			scanf("%d",&i);
			printf("\n请输入要插入的数据：");
			scanf("%d",&n);
			nu_insert_list(head,i,n);
			printf("\n是否还需要插入？    0:打印链表      1：继续插入   2：返回上层菜单    3：返回主菜单。\n");
			scanf("%d",&n);
			printf("\n");
			if(n==0)
				print_list(head);	
			if(n==1)
				goto back3;
			if(n==3)
				return;
			break;
		case 4:
			return;
			break;
	}
goto back;
}

/***********交换排序*********start*****/
//冒泡排序
void bubble_sort(single_Node **head)
{
	int i,j;
	int  len=0;
	int tmp=0;
	single_Node *p=NULL;
	if(*head==NULL)
	{
		printf("单链表为空！无法排序");
		return;
	}
	p=(*head);
	len=p->data;
	for(i=1;i<=len;i++)
	{
		p=(*head);
		for(j=1;j<=len-i;j++)
			{	
				p=p->Next;
				if(p->data>p->Next->data)
				{
					printf("%d 和 %d 交换\n",p->data,p->Next->data);
					tmp=p->Next->data;	
					p->Next->data=p->data;
					p->data=tmp;	
				}
			}
		printf("------------第%d次循环-----------\n",i);
	}
	print_list(head);
}

//快速排序子函数
void quick_sort_sub(single_Node *head,single_Node *end,int *count)
{
	int tmp;
	int i=0;
	static int cc=0;
	single_Node *start,*offset,*move;
	if(head==NULL || head==end)
		return;
	start=head;
	move=head;
	offset=head;
	//if(offset->Next->Next!=NULL )
	offset=offset->Next;
	while(offset !=  end)
	{
		if(start->data  > offset->data)
		{
			move=move->Next;
			printf("交换=%d和%d\n",move->data,offset->data);
			tmp=move->data;
			move->data=offset->data;
			offset->data=tmp;
			//offset=offset->Next;
			
		}
		offset=offset->Next;
		(*count)++;
		printf("第%d次循环,\n",*count);
		
	}
		printf("交换=%d和%d\n",start->data,move->data);
		tmp=start->data;
		start->data=move->data;
		move->data=tmp;
		//*count=*count+i;
		quick_sort_sub(start,move,count);
		quick_sort_sub((move->Next),end,count);
	
}
/*
快速排序
*/
static int c=0;
void quick_sort(single_Node **head)
{	
	
	int *count=&c;
	single_Node *end,*hed;
	if(*head!=NULL|| (*head)->Next!=NULL)
		hed=(*head)->Next;
	else
		printf("单链表空！\n");

	end=(*head)->Next;
	while(end->Next!=NULL)
		end=end->Next;
	quick_sort_sub(hed,end,count);

}

void single_list_swap_sort(single_Node **head)
{
	int n;
back:
	printf("1.冒泡排序\n");
	printf("2.快速排序\n");
	printf("3.退出\n");
	scanf("%d",&n);
	if(n==1)
		bubble_sort(head);
	else if(n==2)
		quick_sort(head);
	else if(n==3)
		return;
	else
		goto back;
}
/**************end*******************/


/***********插入排序**************/


void single_list_insert_sort(single_Node **head)
{
	printf("1.简单插入排序\n");
	printf("2.希尔排序\n");
	printf("3.退出\n");
} 
/*********************************/

/***********选择排序**************/
void single_list_select_sort(single_Node **head)
{
	printf("1.简单选择排序\n");
	printf("2.堆排序\n");
	printf("3.退出\n");
}
/*********************************/

/***********归并排序**************/
void single_list_merge_sort(single_Node **head)
{
	printf("1.二路归并排序\n");
	printf("2.多路归并排序\n");
	printf("3.退出\n");
}
/*********************************/

/***********其他线性排序排序**************/
void single_list_other_sort(single_Node **head)
{
	printf("1.基数排序\n");
	printf("2.桶排序\n");
	printf("3.退出\n");
}
/*********************************/
void sort_option_list(single_Node **head)
{
	int i;
back:
	printf("1.交换排序\n");
	printf("2.插入排序\n");
	printf("3.选择排序\n");
	printf("4.归并排序\n");
	printf("5.其他排序\n");
	printf("6.退出\n");
	scanf("%d",&i);
	if(i==1)
		single_list_swap_sort(head);
	else if(i==2)
		return;	
	else if(i==3)
		return;		
	else if(i==4)	
		return;	
	else if(i==5)	
		return;	
	else if(i==6)
		return;	
	else
		goto back;	
}
/*单链表操作选项菜单*/
void main_option_list(single_Node **head)
{
	int i;
back:
	printf("\n\n\n");
	printf("==============主链表选择菜单==============\n");
	printf("1.创建单链表\n");
	printf("2.插入单链表\n");
	printf("3.删除单链表\n");
	printf("4.单链表排序\n");
	printf("5.单链表环相关操作\n");
	printf("6.打印单链表\n");
	printf("7.退出\n");
	printf("=======================================\n");
	printf("\n");
	printf("\n请输入数字：");
	scanf("%d",&i);
	printf("\n");
	switch(i)
	{
		case 1:
			create_list_head(head);  //创建
			break;
		case 2:
			insert_option_list(head); //插入
			break;
		case 3:
			delete_option_list(head); //删除
			break;
		case 4:
			sort_option_list(head);
			break;
		case 5:
			loop_option_list(head); //单链表环
			break;
		case 6:
			print_list(head);
			break;
		case 7:
			return;
			break;
		default:
			return;
	}
	goto back;
}

void single_list(single_Node **head)
{
  main_option_list(head);
}


